A process in which information is embedded in material for the purpose of identifying the material is known as watermarking. Watermarking can provide a facility for identifying a recipient of a particular version of the material. As such, if the material is copied or used in a way, which is inconsistent with the wishes of the distributor of the material, the distributor can identify the material version from the identification code word and take appropriate action.
In this description, an item of material, which is copied or used in a way, which is inconsistent with the wishes of the originator, owner, creator or distributor of the material, will be referred to for convenience as an offending item of material or offending material. The material could be any of video, audio, audio/video material, software programs, digital documents or any type of information bearing material.
Any watermarking scheme should be arranged to make it difficult for users receiving copies of the same material to collude to either mask a watermark code word or alter a watermark code word. A watermarking scheme should therefore with high probability identify a marked material item, which has been the subject of a collusion attack. This is achieved by identifying a code word recovered from the offending material. Conversely, there should be a low probability of not detecting a code word when a code word is present (false negative probability). In addition the probability of falsely detecting a user as guilty of taking part in a collusion attack, when this user has not taken part, should be as low as possible (false positive probability).
U.S. Pat. No. 5,664,018 discloses a watermarking process in which a plurality of copies of material items are marked with a digital watermark formed from a code word having a predetermined number of coefficients. The watermarked material item is for example an image. The apparatus for introducing the watermark transforms the image into the Discrete Cosine Transform (DCT) domain. The digital watermark is formed from a set of randomly distributed coefficients having a normal distribution. In the DCT domain each code word coefficient is added to a corresponding one of the DCT coefficients. The watermarked image is formed by performing an inverse DCT. A related publication entitled “Resistance of Digital Watermarks to Collusion Attacks”, by J. Kilian, F. T. Leighton et al, published by MIT, Jul. 27, 1998, provides a detailed mathematical analysis of this watermarking process to prove its resistance to attack. Co-pending UK patent applications 0129865.2, 0129841.3, 0129840.5, 0129907.2 and 0129836.3 disclose encoding and detecting apparatus and methods which aim to provide a practical watermarking system, which utilises code words having coefficients which are randomly distributed as proposed in U.S. Pat. No. 5,664,018.